package 笔试.未来.thr;


import org.junit.Test;

import static MyUtils.MHUtils.*;

public class Main {
    @Test
    public void test() {
        int[][] g = {
                {0,1,0},
                {2,0,0},
        };
        System.out.println(countPath(g,2,3));
    }
    int[][] map;
    int n,m;
    int resC=0;
    int[][] vis;
    public int countPath(int[][] map, int n, int m) {
        vis=new int[n][m];
        this.map=map;
        this.n=n;this.m=m;

        int[] qd=new int[2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j]==1){
                    qd[0]=i;qd[1]=j;
                }
            }
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(map[i][j]==2){
                    if(i>=qd[0]&&j<=qd[1])this.fx= new int[][]{{0, -1}, {1, 0}};
                    if(i>=qd[0]&&j>qd[1])this.fx= new int[][]{{0, 1}, {1, 0}};

                    if(i<qd[0]&&j<=qd[1])this.fx= new int[][]{{0,-1}, {-1, 0}};
                    if(i<qd[0]&&j>qd[1])this.fx= new int[][]{{0,1}, {-1, 0}};
                }
            }
        }
        backTrack(qd[0],qd[1]);

        return resC;
    }
    int[][] fx;
    public void backTrack(int i,int j) {
        if(map[i][j]==2){
            resC++;
            return;
        }
        for (int k = 0; k < fx.length; k++) {
            int x = i+fx[k][0], y = j+fx[k][1];
            if(x<0 || x>=n || y<0 || y>=m || map[x][y]==-1|| vis[x][y]==1) {
                continue;
            }
            vis[i][j]=1;
            backTrack(x, y);
            vis[i][j]=0;
        }
    }
}


